#include <bits/stdc++.h>

using namespace std;

/**
 * @param nums: A list of integers
 * @return: A integer indicate the sum of max subarray
 */
int minSubArray(vector<int> &nums)
{
    // write your code here
    if(nums.empty())
        return 0;
    int sum = 0, minSum = INT_MAX;
    for(int i = 0; i < nums.size(); i++){
        sum += nums[i];
        if(sum < minSum)
            minSum = sum;
        if(sum > 0)
            sum = 0;
    }
    return minSum;
}

int main()
{
    vector<int> nums = {1, -1, -2, 1};
//    nums = {-2};
//    nums = {};
//    nums = {5};
//    nums = {-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-4,5,-1000};
    printf("%d", minSubArray(nums));
    return 0;
}

/**
最小子数组

给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。
注意事项

子数组最少包含一个数字
您在真实的面试中是否遇到过这个题？
样例

给出数组[1, -1, -2, 1]，返回 -3

*/

/**
算法思想：参考tran41
贪心法，复杂度O（n）

将子串和为正数的子串丢掉，只留和为负的子串。

参考：https://blog.csdn.net/sinat_30440627/article/details/54924737
*/
